import random
import time
from clicks import time_elapsed

def bubble_sort(arr):
    """
    对输入的列表进行冒泡排序

    参数:
        arr (list): 要排序的列表

    返回:
        None: 列表在原地排序
    """
    # 获取列表长度
    n = len(arr)

    # 遍历所有元素
    for i in range(n):
        # 从第一个元素到最后一个元素，比较相邻元素
        for j in range(0, n - i - 1):
            # 如果当前元素大于下一个元素
            if arr[j] > arr[j + 1]:
                # 交换它们的位置
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

@time_elapsed
def quick_sort(arr):
    low, high = 0, len(arr) - 1
    if low < high:
        stack = [(low, high)]
        while stack:
            low, high = stack.pop()
            pivot = partition(arr, low, high)
            if pivot - 1 > low:
                stack.append((low, pivot - 1))
            if pivot + 1 < high:
                stack.append((pivot + 1, high))

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1


@time_elapsed
def tim_sort(arr):
    """
    使用 TimSort 算法对数组进行排序。

    参数:
        arr (list): 要排序的数组。

    返回:
        None: 数组在原地排序。
    """
    # 最小运行大小
    min_run = 32
    n = len(arr)

    # 对每个最小运行大小的子数组进行插入排序
    for i in range(0, n, min_run):
        insertion_sort(arr, i, min((i + min_run - 1), n - 1))

    # 逐步增加运行大小，进行归并排序
    size = min_run
    while size < n:
        for start in range(0, n, size * 2):
            mid = start + size - 1
            end = min((start + size * 2 - 1), (n - 1))
            # 合并两个已排序的子数组
            merged_array = merge(
                arr[start:mid + 1], arr[mid + 1:end + 1])
            # 将合并后的数组替换原数组的对应部分
            arr[start:start + len(merged_array)] = merged_array
        # 运行大小翻倍
        size *= 2



def insertion_sort(arr, left, right):
    for i in range(left + 1, right + 1):
        key = arr[i]
        j = i - 1
        while j >= left and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

def merge(left, right):
    """
    合并两个已排序的数组。

    参数:
        left (list): 第一个已排序的数组。
        right (list): 第二个已排序的数组。

    返回:
        list: 合并后的已排序数组。
    """
    result = []  # 初始化结果数组
    i = j = 0  # 初始化两个数组的索引

    # 比较两个数组的元素，将较小的元素添加到结果数组中
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    # 将剩余的左半部分元素添加到结果中
    result += left[i:]
    # 将剩余的右半部分元素添加到结果中
    result += right[j:]

    return result


def generate_random_array(size):
    """
    生成一个指定大小的随机整数数组。

    参数:
        size (int): 数组的大小。

    返回:
        list: 包含随机整数的数组。
    """
    return [random.randint(1, 1000) for _ in range(size)]


if __name__ == "__main__":
    array_size = 100000
    test_array = generate_random_array(array_size)

    random.shuffle(test_array)
    quick_sort(test_array)

    random.shuffle(test_array)
    tim_sort(test_array)
